【题解】 [SCOI2008]奖励关状压DP luoguP2473

发现数据范围很小，并且涉及到”集合”，很容易可以想到用状压 $\texttt{DP}$ 。

设 $f[i][j]$ 表示已经抛出了 $i$ 次宝物，获得的宝物集合为 $j$ 时的最优分值。那么转移的时候枚举每一个宝物，分两种情况即可——选当前宝物或者不选。注意选当前宝物的前提是必须满足前提，按照最优情况选取即可。注意最后将所有的宝物的贡献加上后还需要$/n$ ，因为题目要求的是”平均”。

Code:

#include <cstdio>
#include <iostream>
using namespace std;
double f[101][65540];
int p[18],d[18],v[18],N,K;
int main() {
    for(int i=1;i<=16;++i) p[i]=1<<(i-1);
    scanf("%d%d",&K,&N);
    for(int i=1;i<=N;++i) {
        int x;scanf("%d%d",&v[i],&x);
        while(x) {d[i]|=p[x];scanf("%d",&x);}
    }
    for(int i=K;i;--i) /*倒着枚举会好些*/
        for(int j=0;j<=p[N+1]-1;++j) {
            /*上面两重循环枚举状态*/
            for(int k=1;k<=N;++k)/*枚举所有宝物并计算贡献*/
                if((d[k]&j)==d[k]) /*可以选取当前宝物*/
                    f[i][j]+=max(f[i+1][j],f[i+1][j|p[k]]+v[k]);
                    /*按照最优选取*/
                else f[i][j]+=f[i+1][j]; /*不能选取直接转移*/
            f[i][j]/=N;/*所谓"平均"*/
        }
    printf("%.6f\n",f[1][0]);/*最终答案*/
    return 0;
}

本文标题:【题解】 [SCOI2008]奖励关状压DP luoguP2473

文章作者:Qiuly

发布时间:2019年04月23日 - 00:00

最后更新:2019年04月24日 - 15:47

原始链接:http://qiulyblog.github.io/2019/04/23/[题解]luoguP2473/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。